import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class _5有效的括号 {
    /*
    复杂度分析
    时间复杂度：O(n)，其中 nnn 是字符串 sss 的长度。
    空间复杂度：O(n+∣Σ∣)，其中 Σ表示字符集，本题中字符串只包含 6种括号，∣Σ∣=6。栈中的字符数量为 O(n)，而哈希表使用的空间为 O(∣Σ∣)，相加即可得到总空间复杂度。
     */
    public boolean isValid(String s) {
        int n = s.length();
        if(n % 2 == 1){
            return  false;
        }
        Map<Character, Character> map = new HashMap<Character, Character>() {{
            // 将 })] 作为key
            put('}', '{');
            put(']', '[');
            put(')', '(');
        }};
        // 新建一个栈
        LinkedList<Character> stack = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            // 如果c是 })], 则判断， 否则说明是({[ , 直接入栈
            if(map.containsKey(c)){
                // stack.peek() 获取栈顶元素
                if(stack.isEmpty() || stack.peek() != map.get(c)){
                    return false;
                }
                // 将栈顶移除(先进后出，栈顶是最接近 c 的左括号)
                stack.pop();
            }else{
                // 说明c是({[ , 直接入栈
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}
